/**
 * Created by ChangJiabo
 * on 19-5-23 下午7:52.
 */
public class FindMedianSortedArrays {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int target1 = 0, target2 = 0;
        boolean isDouble = true;
        if ((m + n) % 2 != 0) {
            isDouble = false;
        }
        int pos1 = m - 1;
        int pos2 = n - 1;
        int totalNum = (m + n) / 2 + 1;
        if (m == 0) {
            return isDouble ? (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0 : nums2[n / 2];
        } else if (n == 0) {
            return isDouble ? (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0 : nums1[m / 2];
        }
        int[] result = new int[totalNum];
        int i = 0;
        while (i < totalNum) {
            if (pos1 < 0) {
                result[i++] = nums2[pos2--];
                continue;
            }
            if (pos2 < 0) {
                result[i++] = nums1[pos1--];
                continue;
            }
            if (nums1[pos1] > nums2[pos2]) {
                result[i++] = nums1[pos1];
                pos1--;
            } else {
                result[i++] = nums2[pos2];
                pos2--;
            }
        }

        if (isDouble) {
            target1 = result[result.length - 1];
            target2 = result[result.length - 2];
            return (target1 + target2) / 2.0;
        } else {
            target2 = result[result.length - 1];
            return target2;
        }

    }

    /*public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int size = len1 + len2;
        if(size % 2 == 1)
            return findKth(nums1, 0, len1, nums2, 0, len2, size / 2 + 1);
        else
            return (findKth(nums1, 0, len1, nums2, 0, len2, size / 2)
                    + findKth(nums1, 0, len1, nums2, 0, len2, size / 2 + 1)) /2;
    }

    public double findKth(int[] nums1, int start1, int len1, int[] nums2, int start2, int len2, int k)
    {
        if(len1 - start1 > len2 -start2)  // 传进来的时候统一让短的数组为nums1
            return findKth(nums2, start2, len2, nums1, start1, len1, k);

        if(len1 - start1 == 0)  // 表示nums1已经全部加入前K个了，第k个为nums2[k - 1];
            return nums2[k - 1];

        if(k == 1)
            return Math.min(nums1[start1], nums2[start2]);
        // k==1表示已经找到第k-1小的数，下一个数为两个数组start开始的最小值

        int p1 = start1 + Math.min(len1 - start1, k / 2); // p1和p2记录当前需要比较的那个位

        int p2 = start2 + k - p1 + start1;

        if(nums1[p1 - 1] < nums2[p2 - 1])
            return findKth(nums1,  p1, len1, nums2, start2, len2, k - p1 + start1);
        else if(nums1[p1 - 1] > nums2[p2 -1])
            return findKth(nums1, start1, len1, nums2, p2, len2, k - p2 + start2);
        else
            return nums1[p1 - 1];
    }*/

    public static void main(String[] args) {
        int[] a = {1};
        int[] b = {1};
        double r = new FindMedianSortedArrays().findMedianSortedArrays(a, b);
        System.out.println(r);
    }

}
